package tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class 二叉树的序列化与反序列化_297 {
}

/**
 * bfs的queue中  上一层节点始终在下一层节点前  且poll() 出来的顺序  等于每行从左往右排列
 * 用bfs重点：
 *     null需要序列化标记占位  [1,2,3,null,null,4,5]  -> [1,2,3,null,null,4,5,null,null,null,null]  组成一颗完整的二叉树
 *     反序列化的时候新建的子节点加到queue中  每次查看完整树的一个节点并处理  每次都要 idx++
 */
class Codec_bfs {

    public String serialize(TreeNode root) {
        if(root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder zip = new StringBuilder();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null ) {
                zip.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                zip.append("null,");  // 前几行offer进来的节点为空  说明没有节点   不用再offer
            }
        }
        zip.deleteCharAt(zip.lastIndexOf(","));
        return zip.toString();
    }

    /**
     * 不为空就添加节点
     *
     * bfs序列化较简单   难得是反序列化
     * 反序列化和证序列化一样  都是先offer  层序遍历并添加 left  和  right
     * 重点 43/48行  为null  不offer  不用添加子节点  保持和serialize下标索引一致
     */
    public TreeNode deserialize(String data) {
        if(data == "") return null;
        String[] dataArr = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(dataArr[0]));
        queue.offer(root);
        int idx = 1;
        String next;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            next = dataArr[idx++];
            if(!"null".equals(next)) {
                node.left = new TreeNode(Integer.parseInt(next));
                queue.offer(node.left);
            }
            next = dataArr[idx++];
            if(!"null".equals(next)) {
                node.right = new TreeNode(Integer.parseInt(next));
                queue.offer(node.right);
            }
        }
        return root;
    }
}


class Codec_dfs {  //  [1,2,3,null,null,4,5]  -> 1,2,None,None,3,4,None,None,5,None,None   非完全二叉树  递归碰到None 直接返回 不需要层级遍历
    /**
     * 经典的分支递归思路  先序遍历 中左右 最简单的写法
     */
    public String serialize(TreeNode root) {
        if(root == null){ return "None"; }
        String s = root.val + "," + serialize(root.left) + "," + serialize(root.right);
        return s;
    }

    public TreeNode deserialize(String data) {
        String[] dataArr = data.split(",");
        Queue<String> queue = new LinkedList<>(Arrays.asList(dataArr)); // 如果使用list  还需要每次清除队首元素  或者带一个索引  不如queue
        return dfs(queue);
    }

    private TreeNode dfs(Queue<String> queue) {  // 不考虑判空 null  因为最后一个元素一定是 None
        String str = queue.poll();
        if("None".equals(str)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(str));
        root.left = dfs(queue); // 左边碰到None 返回才去看右边  直到碰到None
        root.right = dfs(queue);
        return root;
    }
}

